#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        int l=s.size();
        vector<bool> f(l+1, false);
        f[0]=true;
        for (int i=0;i<l;i++)
            if (f[i]) {
                for (unordered_set<string>::iterator it=dict.begin();it!=dict.end();it++) {
                    bool match=true;
                    for (int k=0;k<it->size() && match;k++)
                        if (i+k>=s.size() || s[i+k]!=(*it)[k]) match=false;
                    if (match && i+it->size()<=s.size())
                        f[i+it->size()]=true;
                }
            }
        return f[l];
    }
};
